package xiaohui;

import java.util.Arrays;

public class CountSortTest {
    public static void main(String[] args) {
        optimizeV2();
    }

    public static void normal() {
        int max = 10;
        int[] array = new int[]{4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10};
        int[] sort = new int[max + 1];
        for (int i = 0; i < array.length; i++) {
            sort[array[i]]++;
        }
        int index = 0;
        for (int i = 0; i < sort.length; i++) {
            for (int j = 0; j < sort[i]; j++) {
                array[index++] = i;
            }
        }
        System.out.println(Arrays.toString(array));
    }

    public static void optimize() {
        int[] array = new int[]{95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        int max = 99, min = 90;
        int diff = max - min;
        int[] sort = new int[diff + 1];
        for (int i = 0; i < array.length; i++) {
            sort[array[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < sort.length; i++) {
            for (int j = 0; j < sort[i]; j++) {
                array[index++] = i + min;
            }
        }
        System.out.println(Arrays.toString(array));
    }

    public static void optimizeV2() {
        int[] array = new int[]{95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        int max = 99, min = 90;
        int diff = max - min;
        int[] sort = new int[diff + 1];
        for (int i = 0; i < array.length; i++) {
            sort[array[i] - min]++;
        }
        for (int i = 1; i < sort.length; i++) {
            sort[i] = sort[i] + sort[i - 1];
        }
        int[] sortedArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            sortedArray[sort[array[i] - min] - 1] = array[i];
            sort[array[i] - min]--;
        }
        System.out.println(Arrays.toString(sortedArray));
    }
}
